package algorithm_learn.operateArray;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Code01_find {
    //arr有序 <=num 最右
    public static int mostRightNoLessNumIndex(int[] arr,int num){
        if(arr==null||arr.length==0){
            return -1;
        }
        int L = 0;
        int R = 0;
        int ans = -1;
        while(L <= R){
            int mid = (L+R)/2;
            if(arr[mid]<num){
                R = mid - 1;
            }
            else {
                ans = mid;
                //arr[mid]>=num
                L = mid + 1;
            }
        }
        return ans;
    }

    //arr有序 >=num 最左
    public static int mostLeftNoLessNumIndex(int[] arr,int num){
        if(arr==null||arr.length==0){
            return -1;
        }
        int L = 0;
        int ans = -1;
        int R = arr.length-1;
        while (L <= R){
            // ans 更新
            int mid = (L + R)/2;
            if(arr[mid] >= num){
                //记下位置
                ans = mid;
                //往左砍
                R = mid -1;
            }
            else {
                //arr[mid] < num)
                //往右边砍
                L = mid + 1;
            }
        }
        return ans;
    }


    //保证arr有序 二分查找
    public static boolean find(int[] arr,int num){
        if(arr==null || arr.length==0){return false;}
        int L = 0;
        int R = arr.length - 1;
        while(L <= R){
            int mid = (L + R)/2;
            if(arr[mid] == num){
                return true;
            }else if(arr[mid] < num){
                L = mid + 1;
            }else {
                R = mid - 1;
            }
        }
        return false;
    }
    //写一个遍历方法
    public static boolean test(int[] sortedArr,int num){
        for (int cur : sortedArr){
            if(cur==num){
                return true;
            }
        }
        return false;
    }
    //随机生成数组
    public static int[] generateRandomArray(int maxSize,int maxValue){
        int[] arr = new int[(int)((maxSize+1)*Math.random())];
        for(int i = 0;i<arr.length;i++){
            arr[i] = (int)((maxValue+1) * Math.random()) - (int)(maxValue * Math.random());
        }
        return arr;
    }
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for(int i=0;i<testTime;i++){
            int[] arr = generateRandomArray(maxSize,maxValue);
            Arrays.sort(arr);
            int value = (int)((maxValue+1) * Math.random()) - (int)(maxValue * Math.random());
            if(test(arr,value) != find(arr,value)){
                System.out.println("error");
                succeed = false;
                break;
            }
        }
        System.out.println(succeed?"NICE":"FUCKING");
    }
}
